﻿#include <iostream>
#include <queue>
using std::cout;
using std::endl;

struct Node {
  Node* left;
  Node* right;
  char data;

  Node(char data_init, Node* left_init = NULL, Node* right_init = NULL) {
    data = data_init;
    left = left_init;
    right = right_init;
  }
};

class BinaryTree {
 public:
  BinaryTree() : root(NULL) { Init(); }
  ~BinaryTree() { Delete(&root); }

  void Init() {
    Node* level1 = new Node('a');
    root = level1;
    Node* level21 = new Node('b');
    Node* level22 = new Node('c');
    level1->left = level21;
    level1->right = level22;
    Node* level31 = new Node('d');
    Node* level32 = new Node('e');
    level21->left = level31;
    level21->right = level32;
    Node* level33 = new Node('f');
    Node* level34 = new Node('g');
    level22->left = level33;
    level22->right = level34;
  }

  void Delete(Node** pnode) {
    if (pnode == NULL) return;
    Node* node = *pnode;
    if (node == NULL) return;
    Delete(&(node->left));
    Delete(&(node->right));
    delete node;
    *pnode = NULL;
  }
  void DeleteRef(Node*& node) {
    if (node == NULL) return;
    DeleteRef(node->left);
    DeleteRef(node->right);
    delete node;
    node = NULL;
  }

  Node* GetRoot() const { return root; }
  Node** GetRootAddr() { return &root; }
  Node*& GetRootRef() { return root; }

 private:
  Node* root;
};

void PreOrder(Node* root) {
  if (root == NULL) return;
  cout << root->data << ' ';
  PreOrder(root->left);
  PreOrder(root->right);
}

void InOrder(Node* root) {
  if (root == NULL) return;
  InOrder(root->left);
  cout << root->data << ' ';
  InOrder(root->right);
}

void PostOrder(Node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  cout << root->data << ' ';
}

void LevelOrder(Node* root) {
  if (root == NULL) return;
  std::queue<Node*> myq;
  myq.push(root);
  while (myq.size() > 0) {
    Node* node = myq.front();
    myq.pop();
    cout << node->data << ' ';
    if (node->left) myq.push(node->left);
    if (node->right) myq.push(node->right);
  }
}

int main() {
  BinaryTree tree;

  PreOrder(tree.GetRoot());
  cout << endl;

  InOrder(tree.GetRoot());
  cout << endl;

  PostOrder(tree.GetRoot());
  cout << endl;

  LevelOrder(tree.GetRoot());
  cout << endl;

  // tree.Delete(tree.GetRootAddr());
  tree.DeleteRef(tree.GetRootRef());
  LevelOrder(tree.GetRoot());

  return 0;
}